package t_1202

import "sort"

func smallestStringWithSwaps(s string, pairs [][]int) string {
	parent := make([]int, len(s))
	group := make(map[int][]int)
	for i := range s {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if x != parent[x] {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}

	union := func(x, y int) {
		parent[find(x)] = find(y)
	}

	// 构建并查集
	for _, pair := range pairs {
		union(pair[0], pair[1])
	}

	// 根据并查集。同根分组排序
	for i := range s {
		gi := group[find(i)]
		gi = append(gi, i)
		group[find(i)] = gi
	}

	for gk := range group {
		sort.Slice(group[gk], func(i, j int) bool { return s[group[gk][i]] < s[group[gk][j]] })
	}

	// 每次推出最小值
	var res []byte
	for i, _ := range s {
		mini := find(i)
		minr := s[group[mini][0]]
		group[mini] = group[mini][1:]
		res = append(res, minr)
	}

	return string(res)
}
